package Simple3;

import java.util.Stack;


public class skyLine {
	
	public skyLine(){
		
	}
	
	public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int[] input = new int[height.length+1];
        int i = 0, ret = 0;
        for(;i<height.length;i++)
            input[i]=height[i];
        input[height.length]=0;
        
        i=0;
        while(i<input.length){
            if(stack.isEmpty() || input[stack.peek()]<=input[i]){
                stack.push(i++);
            }
            else{
                int temp = stack.pop();
                ret = Math.max(ret, input[temp]*(stack.isEmpty() ? i : i-stack.peek()-1));
            }
        }
        return ret;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		skyLine sk_test = new skyLine();
		int[] test = {2,1,5,6,2,3};
		System.out.println(sk_test.largestRectangleArea(test));
	}

}
